863F - Almost Permutation - CodeForces Solution

import math
import heapq
import math


class MCF:
    def __init__(self):
        self.edges = {}
        self.edge_indexes = {}
        self.source = 0
        self.sink = 1
        self.nodes = set()
        self.sources = set()
        self.sinks = set()
        self.visiting = dict()
        self.dijkstra_path = dict()
        self.flow_iteration = -1
        self._add_node(self.source)
        self._add_node(self.sink)
        self.cost = 0

    def add_edge(self, origin, destination, cost, capacity):
        if origin not in self.nodes:
            self._add_node(origin)
        if destination not in self.nodes:
            self._add_node(destination)
        self.edges[origin][destination] = [cost, capacity]
        self.edge_indexes[len(self.edge_indexes)] = self.edges[origin][destination]
        self.edges[destination][origin] = [cost, 0]

    def add_source(self, source):
        self.sources.add(source)

    def add_sink(self, sink):
        self.sinks.add(sink)

    def solve(self):
        self._add_arcs_from_main_source_to_sources()
        self._add_arcs_from_sinks_to_main_sink()
        while self._dijkstra():
            self._apply_flow()

    def get_flow(self):
        return self.flow_iteration

    def _add_node(self, node):
        self.nodes.add(node)
        self.edges[node] = {}
        self.visiting[node] = -1
        self.dijkstra_path[node] = -1

    def _add_arcs_from_main_source_to_sources(self):
        for source in self.sources:
            self.add_edge(self.source, source, 0, math.inf)

    def _add_arcs_from_sinks_to_main_sink(self):
        for sink in self.sinks:
            self.add_edge(sink, self.sink, 0, math.inf)

    def _dijkstra(self):
        heap = []
        heapq.heappush(heap, (0, self.source))
        self.flow_iteration += 1
        distances = {node: math.inf for node in self.nodes}
        distances[self.source] = 0
        while len(heap) > 0:
            (distance, node) = heapq.heappop(heap)
            if node in self.sinks:
                self.dijkstra_path[self.sink] = node
                return True
            if self.flow_iteration != self.visiting[node]:
                self.visiting[node] = self.flow_iteration
                for neighbor, [cost, capacity] in self.edges[node].items():
                    if capacity > 0 and distances[neighbor] > distance + cost:
                        self.dijkstra_path[neighbor] = node
                        distances[neighbor] = distance + cost
                        heapq.heappush(heap, (distance + cost, neighbor))
        return distances[self.sink] != math.inf

    def _apply_flow(self):
        iterator = self.sink
        while iterator != self.source:
            previous_node = self.dijkstra_path[iterator]
            self.edges[previous_node][iterator][1] -= 1
            self.edges[iterator][previous_node][1] += 1
            if previous_node in self.sources:
                self.cost += self.edges[previous_node][iterator][0]
            iterator = previous_node


def get_inputs():
    n, q = [int(number) for number in input().split()]
    Lower = [0] * n
    Upper = [n-1] * n
    for i in range(q):
        t, l, r, v = [int(number) for number in input().split()]
        for j in range(l-1, r):
            if t == 1:
                Lower[j] = max(Lower[j], v-1)
            else:
                Upper[j] = min(Upper[j], v-1)
    return n, Lower, Upper


mcf = MCF()

n, Lower, Upper = get_inputs()

src = 2
sink = 3
for i in range(n):
    for j in range(1, n + 1):
        mcf.add_edge(src, 2500 + n * n + n * i + j, 2 * j - 1, 1)
        mcf.add_edge(2500 + n * n + n * i + j, i + 4, 2 * j - 1, 1)
    mcf.add_edge(i + 4 + n, sink, 0, 1)
    for j in range(Lower[i], Upper[i]+1):
        mcf.add_edge(j + 4, i + n + 4, 0, 1)

mcf.add_source(src)
mcf.add_sink(sink)
mcf.solve()

if mcf.get_flow() == n:
    print(mcf.cost)
else:
    print(-1)